1. Field of the Invention
The present invention generally relates to electronic circuits and, more specifically, to circuits executing modular exponentiation calculations according to an RSA-CRT algorithm.
The present invention more specifically applies to the protection, against piracy attempts, of a quantity (digital word), said to be private or secret, used in the process of data protection, or of authentication or identification of an electronic device (for example, a smart card or an electronic card comprising one or several integrated circuits).
The present invention especially relates to the scrambling of the execution of an RSA-CRT algorithm. “Scrambling” is used to designate a modification in the observable physical characteristics (consumption, thermal or electromagnetic radiation, etc.) induced by the operation of the electronic device executing the calculation.
2. Discussion of the Related Art
FIG. 1 very schematically shows a smart card 1 of the type to which the present invention applies as an example. Such a card 1 is formed of a support material (generally made of plastic matter) supporting or enclosing one or several electronic circuits 10. Circuit 10 communicates with the outside by means of contacts 2, connectable to a read or read/write terminal. Circuit 10 may also be associated with contactless transmission-reception means and communicate wirelessly with a terminal (be it by a hertzian or electromagnetic radiation).
FIG. 2 very schematically shows in the form of blocks an example of an electronic circuit 10 of the type to which the present invention applies. Such a circuit, for example, is that of a smart card such as shown in FIG. 1. According to another example, this circuit is assembled on an electronic board with other integrated circuits.
Circuit 10 comprises a processing unit 11 (PU), for example, a central processing unit, communicating within circuit 10 and via one or several data, address, and control buses 15, at least with one or several volatile and/or non-volatile memories 12 (MEM) and with an input/output circuit 13 (I/O). Circuit 13 is used as an interface for communication, with or without contact, with the outside of circuit 10. Most often, circuit 10 comprises other software and/or hardware functions, symbolized in FIG. 2 by a block 14 (FCT) connected to bus 15.
In a circuit 10 to which the present invention applies as an example, processing unit 11 or one of functions 14 is able to execute an algorithmic processing on digital data by implementing an algorithm known as RSA-CRT. The term “data” is used to designate any quantity exploitable by processing unit 11 or a secondary function 14, be they program instructions, addresses, actual data, controls, etc.
The RSA algorithm is an asymmetrical algorithm implementing one or several modular exponentiations and using at least two digital quantities to cipher/decipher or sign/verify data. Such quantities are called the public key (noted e) and the private key (noted d). Such an algorithm is described, for example, in work “Handbook of Applied Cryptography” by Alfred J. Menezes, Paul C. Van Oorschot, and Scott A. Vanstone, published by CRC Press in 1997, pp. 285-286.
Keys d and e are selected so that their modular multiplication, modulo φ(n), is equal to 1 ((e*d)=1 mod φ(n)), where φ represents the Euler function and n the RSA modulo. The result, noted A mod b, of a modular operation (addition, multiplication, exponentiation, etc.) corresponds to the rest of the Euclidean division of A by b (b is called the modulo).
In the RSA, a ciphering of a message M comprises the calculation of a ciphered message C as being the result of modular exponentiation Me mod n. A deciphering of a message C comprises recovering clear message M as being the result of modular exponentiation Cd mod n. A calculation of a signature S of a message M comprises calculating modular exponentiation Md mod n. A verification of a signature S comprises calculating modular exponentiation Se mod n to verify that message M can effectively be recovered.
In all cases, the case in point is to perform a modular exponentiation of exponent z and of modulo n from a datum Y (X=Yz mod n).
FIG. 3 illustrates, in a very simplified flowchart, an example of implementation of the RSA algorithm by applying the Chinese remainder theorem, an example of which is described in the above-mentioned work (page 612).
Such an implementation aims at accelerating the calculation of quantity X=Yz mod n by performing two partial modular exponentiations, by using two relatively prime integers p and q, such that their product p*q is equal to quantity n and that the result of the multiplication of the public and private keys is equal to one modulo (p−1)*(q−1) ((e*d)=1 mod ((p−1)*(q−1))). The smallest quantity between p and q is generally noted q. Quantities p and q should remain unknown from the outside since they provide information about the private key.
A first phase (block 21) comprises calculating two quantities z′ and z″ from the n modulo, from its factors p and q, and from key z, as follows:
z′=z mod(q−1); and
z″=z mod(p−1).
Quantities z′ and z″ are modular reductions modulo q−1, respectively p−1, of quantity z. They are either calculated on the fly, that is, for each new exponentiation calculation, or precalculated and stored in memories of circuit 10.
A second phase (block 22) is a first modular exponentiation calculation of a quantity X′ equal to Yz′ mod q. In the case where quantities z′ and z″ have been precalculated and recorded, the introduction of datum Y intervenes for the execution of phase 22.
A third phase is a second modular exponentiation calculation (block 23) of a quantity X″ equal to Yz″ mod p, followed by the implementation (block 24) of a so-called recombination function h, having quantities X′, X″, p, q, and (q−1 mod p) as operands. Quantity q−1 mod p may have been precalculated at the same time as quantities z′ and z″ (block 21) and stored.
Function h comprises calculating the difference between partial results X″ and X′, multiplying this difference by quantity q−1 mod p, then the obtained result by number q before adding partial result X″. This amounts to executing the following equation:X=[(X″−X′)*(q−1 mod p)]*q +X′. 
In practice, the calculation may take other forms, provided the result to respects that of the above equation.
For example, since p and q are relatively prime, this calculation can be written as:X=[(p−1 mod q)*p*X′(q−1 mod p)*q*X″]mod n,since:(p−1 mod q)*p=1−(q−1 mod p)*q. 
Steps 23 and 24 have been illustrated in the same phase since, in the illustrated case, they are executed in the same operator (software or hardware) while step 22 is executed by another operator. However, other implementations are possible. For example, steps 22 to 24 may also be executed by three different operators. Steps 22 and 23 may also be executed by the same operator loaded with different operands.
A disadvantage is that an execution by an electronic circuit of an RSA-CRT-type algorithm is sensitive to attacks by analysis of the consumption of the circuit executing it. In particular, such an execution is sensitive to attacks known as SPA (simple power analysis). Such attacks comprise having the calculations executed on specific data, which enable going back to the factorization of n (p and q). Now, the knowing of quantities p and q enables finding the private key.
It has already been provided to scramble the execution of an RSA algorithm by introducing random numbers into the calculation.
An example is described in U.S. patent application No. 2003/0044014. This example comprises introducing random numbers into the modulo of a modular exponentation calculation. Such a process is efficient on differential power analyses (DPA) where the attacker selects keys, but poses a problem for SPA-type attacks where the attacker selects data. In particular, the first calculation of the recombination step (block 24) is not protected in the process disclosed in this application. However, it is this calculation (difference between partial results X′ and X″) that is aimed at by an attack by choice of message or data.